Encoding methods, commonly called halftoning, are used to reduce the number of quantization levels per pixel in a digital image while maintaining the gray appearance of the image at normal reading distance. Halftoning techniques are widely employed in the printing and display of digital images. Halftoning techniques are necessary because the physical processes involved are binary in nature or the processes have been restricted to binary operation for reason of cost, speed-memory, or stability in the presence of process fluctuations. Examples of such processes are: most printing presses; ink jet printers; binary cathode ray tube displays; and laser xerography.
In the digital reproduction of documents, image information, be it color, black, or white, is commonly generated in a raster format where the raster comprises a plurality of continuous tone or gray level pixels, i.e., pixels that are defined by digital values, each value representing a gray level among a number of gray levels. Thus, in an 8 bit system, 256 levels of gray are present, where each level represents an increment of gray between white and black. Each separation includes 256 levels of information and there may be more than 16 million colors defined by a gray raster. Usually, rasters in such a gray level format are unprintable by standard printers. Standard printers print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, for example, four in the quaternary case. Accordingly, it is a limited number of levels that are printable. Besides gray level information derived by scanning, certain processing techniques such as those described, for example, in U.S. Pat. No. 5,226,094 to Eschbach, may produce gray level data requiring quantization for printing.
A standard method of quantizing gray level pixel values to binary level pixel values is through dithering or screening processes. In such arrangements, over a given area having a number of gray pixels therein, each pixel value of an array of gray level pixels within the area is compared to one of a set of pre-selected thresholds as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the screen matrix will be exceeded, i.e., the image value at that specific location is larger than the values stored in the dither matrix for that same location where the intensity is less than the threshold the pixel is colored black, while the remaining elements are allowed to remain white, dependent on the actual physical quantity described by the data. The effect of the distribution of black and white over the halftone cell is integrated by the human eye as gray. A trade-off is required between the number of gray level increments representable by a screen cell, versus the size or frequency of the cell. While it is desirable to have as many gray levels as possible representable by a screen cell, such a requirement increases the size of the cell until its repetition across an image becomes visible. However, with a smaller cell, which can be repeated at high frequency across a page, only a relatively small number of gray levels can be represented.
Algorithms that convert gray images to binary or other number of level images without repeating patterns exist, and include among them error diffusion, as taught, for example, in "An Adaptive Algorithm for Spatial Grayscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976). Another more elaborate error diffusion technique is taught by U.S. Pat. No. 5,045,952 to Eschbach. Error diffusion tends to suffer from a characteristic "worming" defect. One method of reducing the worming artifact in an error diffusion process that has been noted is to distribute error along a space filling curve, such as Hilbert, Peano or Murray Curves. See, for example, "Using Peano Curves for Bilevel Display of Continuous-tone Images", by Witten et al., IEEE Comp. Graph. and App. Vol 2, No. 5, pp. 47-52 (1982); "Naive Halftoning" by Cole, Proceedings of CGI '90, Springer Verlag pp. 203-222 (1990); and "Three Plus Five Makes Eight: A simplified Approach to Halftoning" by Wyvill et al., Proceedings of CGI '91 Scientific Visualization of Physical Phenomena, pp. 379-392 (1991). Unfortunately, space filling curves present complex processing order, see, for example, "Digital halftoning with Space Filling Curves" by L. Velho et al., Computer Graphics, Vol. 25 No. 4, pp. 81-90 (1991), while, in view of the operation of printers and most image processors, it would be highly desirable to work in scan line order. Error diffusion is often unusable by certain reproduction processes, such as electrophotography, because it tends to produce isolated spots that are not reproducible. In such cases, screening is used with threshold sets arranged to cluster spots together into larger printable dots. Error diffusion is also an inherently sequential process that does not lend itself to parallel processing, while screening.
It is apparent that halftoning is a well known method for rendering continuous tone images on two-color (e.g. black-and-white) devices--the idea being to produce a gray shade by printing a pattern of black and white spots. There are, however, devices that can produce a number of levels that are still limited, but greater than two levels. For example some display monitors that can produce 4 or 8 graylevels have been built, and an ink-jet printer can print with 4 shades of gray ink. Halftoning has been generalized to support these multilevel devices and a scheme that does this is described in a paper by Pirsch and Netravali entitled "Transmission of Gray Level Images by Multilevel Dither Techniques", Computers & Graphics, Vol. 7, No. 1, pp. 31-44, 1983. Their method constructs gray shades from patterns of two adjacent levels; thus, light shades are produced by patterns of white paper and the lightest gray level. These patterns handle the shades down to the shade produced by entirely covering the area with the light gray level. Darker colors are produced by patterns of the lightest gray level and the next darkest gray level. This scheme is illustrated in FIG. 1 of this disclosure (labeled as prior art).
The multilevel halftoning implementation most related to this disclosure is described in U.S. Pat. No. 5,196,942 to Shiau. Shiau includes computation and propagation of a halftone cell error term. Shiau compares the intensity value of a pixel to a halftone threshold and uses the decision to decide whether further comparisons are needed or if the appropriate gray level has been found. However, Shiau does not mention how one should choose halftone thresholds nor how the technique can be employed to control textures and/or coverage. Control over how much of a given level is used is necessary in the case of ink-jet printing where some gray levels are produced by overprinting of two gray inks. While overprinting may produce a useful level of gray it also places twice as much ink on the paper. When there is too much ink there are problems of bleed, bloom, and cockle.
While the prior art attempts have accomplished halftoning, techniques that can accurately construct patterns from more than two gray levels at a time during multilevel halftoning are lacking. It is therefore an object of the invention to provide a method that can achieve such construction resulting in the minimization of texture contours and the ability to control the halftoning level achieved.
All of the references cited herein are incorporated by reference for their teachings.